#include <bits/stdc++.h>

using namespace std;

// 不需要提交这个类
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 求二叉树的最大深度
// 测试链接 : https://leetcode.cn/problems/maximum-depth-of-binary-tree/
class Solution 
{
public:
    int maxDepth(TreeNode* root) 
    {
        if(root == nullptr) return 0;

        int left = maxDepth(root->left);
        int right = maxDepth(root->right);
        return max(left, right) + 1;
    }
};


// 求二叉树的最小深度
// 测试链接 : https://leetcode.cn/problems/minimum-depth-of-binary-tree/
class Solution 
{
public:
    // bfs
    int minDepth2(TreeNode* root) 
    {
        // 当前的树是空树
        if(root == nullptr) return 0;
        // 当前root是叶节点
        if(root->left == nullptr && root->right == nullptr) return 1;

        int left = INT_MAX, right = INT_MAX;
        if(root->left) left = minDepth2(root->left);
        if(root->right) right = minDepth2(root->right);

        return min(left, right) + 1;
    }

    // bfs
    int minDepth2(TreeNode* root) 
    {
        if(root == nullptr) return 0;

        queue<pair<TreeNode*, int>> q;
        q.emplace(root, 1);
        while(!q.empty())
        {
            auto [node, depth] = q.front();
            q.pop();
            if(!node->left && !node->right) return depth;
            if(node->left) q.emplace(node->left, depth + 1);
            if(node->right) q.emplace(node->right, depth + 1);
        }

        return 0;
    }
};